class Solution(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        s_dict = dict()
        for x in s:
            if x in s_dict:
                s_dict[x] += 1
            else:
                s_dict[x] = 1
        for y in t:
            if y not in s_dict:
                return y
            if s_dict[y] == 0:
                return y
            else:
                s_dict[y] -= 1

class Solution2(object):
    def findTheDifference(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        return list((collections.Counter(t) - collections.Counter(s)))[0]






    """
        Time Complexity = O(n)
        Space Complexity = O(1)

        Given two strings s and t which consist of only lowercase letters.

        String t is generated by random shuffling string s and then add one more letter at a random position.

        Find the letter that was added in t.

        Example:
        Input:
        s = "abcd"
        t = "abcde"

        Output:
        e

        Explanation:
        'e' is the letter that was added.
    """
